\section{Previous work}

\subsection{Haddon and Waite}

In 1967, Haddon and Waite \cite{Haddon:1967} designed the first
algorithm for compacting garbage collection.  The context of their
work was assumed to be an existing mark-and-sweep garbage collector
using a free list, and when that collector fails due to fragmentation,
even though there is enough total space available, their compacting
algorithm would take over and compact the heap.  The cost of their
algorithm was considered unimportant, because the alternative would be
to fail by terminating the program.

Rather than invoking a marking procedure to determine live data, they
imagined using the existing free list to determine areas of available
storage. 

An entry in their break table indicates a start address of a zone of
live data and the total amount of free space below that address.
There are many different possible variations on the exact contents of
the break table, but they are all equivalent.

They show that, if each object requires at least two words of storage,
then the total amount of free space in the entire heap is large enough
to hold the break table.  As a result, no additional space is
required for their technique to work.

\subsection{Other work}

Of the traditional compacting algorithms, three types of algorithms
preserve allocation order; the one by Haddon and Waite
\cite{Haddon:1967}, the so-called Lisp2 algorithm, and the
\emph{threading} algorithms.  The Lisp2 algorithm requires an
additional field the size of a pointer in each object in order to hold
forwarding information.  This field is set after the marking phase.
Pointers are then updated according to this information.  Finally, the
heap is compacted.  Threading algorithms by Fisher \cite{fish74},
Morris \cite{morr78}, and Jonkers \cite{jonk79} work by reversing
pointers.  In their survey of different compacting algorithms, Cohen
and Nicolau \cite{Cohen:1983:CCA:69575.357226} conclude that the Lisp2
algorithm is the fastest.  Threading algorithms perform the worst.

Abuaiadh et al \cite{Abuaiadh:2004:EPH:1028976.1028995} designed a
compaction algorithm that uses forwarding information much like the
Lisp2 algorithm.  However, to avoid the cost of an entire pointer per
object, they use a single word of forwarding information for around
$256$ bytes, which amounts to no more than a few bits per word.
Although reported to be fast, unfortunately, their algorithm does not
preserve the allocation order of objects.  Their paper mentions that
benchmarks have verified the importance of doing so.  They report that
compaction algorithms may cause significant pauses, and their
algorithm reduces these pauses.  The reason for these pauses is no
doubt that the context of their work is a large global heap (they
mention 1GB), whereas the context of the present work is the size of
the nursery (around 4 MB).

Kermany et al \cite{Kermany:2006:CCI:1133981.1134023} describe a
compacting algorithm that uses memory-mapping operations in order to
compact the heap.  Their algorithm is parallel, concurrent, and
incremental.  However, in addition to the cost of marking, moving
objects, and updating pointers, compared to the method described in
this paper, there is an additional cost associated with the
memory-mapping operations, and this cost is is non-negligible.
Forwarding information is handled the same way as in the method used
by Abuaiadh et al.  Like the method described by Haddon and Waite, and
the method presented in this paper, relative allocation order between
the objects is preserved.
